package com.zhj.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 力扣 496 获取第一个数组对应元素，在第二个数组这个数字后最大的数
 * @author zhj
 */
public class Test496 {
    public static void main(String[] args) {
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};
        System.out.println(Arrays.toString(findMax2(nums1, nums2)));
    }

    private static int[] findMax(int[] arr1, int[] arr2) {
        int[] res = new int[arr1.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr2.length; i++) {
            stack.push(arr2[i]);
        }
        for (int i = 0; i < arr1.length; i++) {
            Stack<Integer> temp = new Stack<>();
            int max = -1;
            boolean isFound = false;
            int cur = arr1[i];
            while (!stack.isEmpty() && !isFound) {
                int top = stack.pop();
                if (top > cur) {
                    max = top;
                } else if (top == cur) {
                    isFound = true;
                }
                temp.push(top);
            }
            res[i] = max;
            while (!temp.isEmpty()) {
                stack.push(temp.pop());
            }
        }

        return res;
    }

    private static int[] findMax2(int[] arr1, int[] arr2) {
        int[] res = new int[arr1.length];
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : arr2) {
            while (stack.size() != 0 && i > stack.peek()) {
                int temp = stack.pop();
                map.put(temp, i);
            }
            stack.push(i);
        }
        while (stack.size() != 0) {
            int temp = stack.pop();
            map.put(temp, -1);
        }
        for (int i = 0; i < res.length; i++) {
            res[i] = map.get(arr1[i]);
        }
        return res;
    }
}
